The invention relates to a method and apparatus for scaling traffic engineering, TE, routing in a network, and in particular to a method and apparatus to scale traffic engineering of large networks using a traffic engineering, TE, hierarchical virtualization technique.
Traffic engineering, TE, on a contemporary transport network such as a wavelength division multiplexing, WDM, layer network does present several challenges. One of these challenges is the sheer amount of information data concerning network elements such as WDM reconfigurable optical add drop multiplexers, ROADM, and links interconnecting these network elements, wherein the information data has to be constantly rediscovered and redistributed to network traffic engineering applications in real time. A further challenge is potentially very big size of traffic engineering databases, TED, and therefore high memory and computation power requirements, especially when considering the complexity of employed path computation algorithms such as optical impairment aware path computations performed in WDM layer networks. What makes it even more difficult to meet these challenges is the fact that service paths in the network have often to be computed in real time, especially in the context of specific applications such as network failure service recovery application. With the increasing size of the network these challenges can become exponentially more difficult to address, so that scalable traffic engineering solutions that work with equal success on networks of different sizes become important.
A general principle of achieving a scalable routing solution is to make sure that there is no entity in the network that knows everything about every network element and link, instead, to orchestrate things in such a way that each entity responsible for route calculations gets an access to detailed information on some network elements and links, while summarized or aggregated information on the rest of the network elements and links is provided. The challenge is to define this aggregated information to be, on the one hand, a significantly smaller in size version of the detailed information, while, on the other hand, to be sufficient for each route computing entity to be able to calculate a route to each of possible network destinations. In other words, the challenge is to come up with the right level of abstraction when performing a summarization of routing information data to provide the shortest possible aggregate without losing any information that might be important for the route calculations.
For example, in IP intra-domain routing protocols, IGP, such as OSPF or ISIS, this is achieved by breaking the network in multiple areas and by flooding full router and link state advertisements only within the respective local areas of the network, while summarizing on the area borders the intra-area information in the form of IP prefix aggregates that describe the reachability within the areas, and flood the aggregates across the area borders into neighbouring areas. A final result is that any given OSPF or ISIS speaker can calculate a route to any IP destination located in its local areas, as well as to any IP destination located in remote areas. For example, a conventional multi-area IP network configuration is illustrated in FIG. 1. In this example, a node (network element) 1.1.1.1 has full/detailed information about all nodes and links of area 1 illustrated in FIG. 1. At the same time, this node 1.1.1.1 has information about area 2 in the form of a small amount of IP prefixes describing IP reachability within area 2. The IP prefixes are generated by area border node 1.2.1.1 as shown in FIG. 1 and flooded into area 1 via area 0 with the help of area border node 1.1.1.3. This makes it possible for node 1.1.1.1 to calculate IP routes not only to nodes within area 1 such as to node 1.1.1.5 but also to nodes in the remote area 2, for example, to node 1.2.1.2. This is achieved on the reduced network topology information, which is smaller in size and better manageable compared to one of a flat single-area configuration of the same physical network.
The most popular conventional way to scale the TE routing is to break the network into multiple TE domains and to map each of said domains onto a separate IGP (OSPF or ISIS) area as illustrated in FIG. 2. Because IGP uses the same mechanism to flood both IP routing and TE information, this approach limits the scope of TE information dissemination in the network and hence the traffic engineering database, TED, size on a given IGP speaker, such as node 1.1.1.1 to local to the node areas. The problem with TE routing is the difficulty of TE information aggregation for the following reasons. In contrast to IP routing, which deals only with IP reachability and is concerned only with IP addresses designed specifically to be aggregatable, traffic engineering, TE, routing, which is the process of computing of traffic engineering paths, deals with a much richer set of information about nodes and links within the network. This data is very difficult to summarize without losing details important for the traffic engineering, TE, path calculation. Therefore, inter-domain traffic engineering, TE, paths are commonly computed with no TE visibility into the remote TE domains.
One conventional way of doing so is by using a distributed path computation technique. Specifically, if node 1.1.1.1 located in TE domain 1, as illustrated in FIG. 2, which is to set up a service to node 1.2.1.2 TE domain 2, node 1.1.1.1 can compute a TE path to a border node 1.1.1.3 located on the border between TE domain 1 and TE domain 0, being the next TE domain towards the destination. Then, the node 1.1.1.1 can signal a service setup message along the computed path. When node 1.1.1.3, being the border node, receives the service setup message, it repeats the steps taken on node 1.1.1.1 and computes a path to the border node of the next TE domain towards the destination node, i.e. node 1.2.1.1 and signals the service setup message along the path, and so forth, until the path is computed to the service destination (by node 1.2.1.1). This conventional approach is rather simple, but has some severe deficiencies. On such deficiency is the necessity to know in advance the sequence of TE domains for the resulting path to be traversed. A further deficiency is a potential failure or sub-optimality of the distributed path computation. For example, a path segment chosen for TE domain N may yield no path segment across TE domain N+1 (which may exist should a different path segment across TE domain N has been selected). Yet another deficiency of this conventional approach is the complexity of computation of diverse end-to-end paths for the same service, and even more so, when computing concurrently paths for multiple services with distinct source/destination service termination points.
Another widely used conventional method to compute inter-domain TE paths under conditions of limited or no TE visibility is by using remote path computation elements, PCE, in accordance with the PCE-based architecture (RFC4655). Specifically, if a given node of the network such as node 1.1.1.1, as illustrated in FIG. 3, cannot compute path(s) to a destination located in one of the non-local TE domains because of lack of TE visibility (for example, to node 1.2.1.2), the path computation can be requested from one or more of the path computation elements, PCEs, of the network that supposedly have a better view of the TE domains across which the resulting path(s) will traverse. This conventional approach works exceptionally well when the paths are computed by a path computation element, PCE, that has full visibility in each of the network's TE domains, as shown in FIG. 3. However, in this case it is assumes that a single entity, i.e. the path computation element, PCE, knows all details about every network element and link of the network, which means a violation of the above-mentioned principle of network scalability. Consequently, this sets a limit to the extent the approach can scale. In other words, providing a given path computation element, PCE, with detailed traffic engineering, TE, information on each and every network TE domain does not solve the scalability problem, rather, pushes the problem from the network element to the path computation element, PCE.
It is also possible according to the path computation element, PCE-based network architecture to have several network path computation elements, PCEs, wherein each of them covers a sub-set but not all of the TE domains. Covering means in this context that a given path computation element, PCE, has detailed up-to-date information on a sub-set of TE domains. Consequently, it is possible to orchestrate the cooperation of the path computation elements, PCEs, to satisfy a given inter-domain path computation request as illustrated in FIG. 4. However, organizing such an orchestration, compared with the path computation in a single TE domain, is, generally speaking, extremely complex, cumbersome and computation timewise unpredictable to a point where it becomes totally impractical. To illustrate this, one can consider the example illustrated in FIG. 5, wherein a network is broken into 15 TE domains and wherein the network has 5 path computation elements, PCEs, each of which covering its own set of 3 domains. Suppose, the path computation elements, PCEs, are presented with a request to compute a path between destinations located, for example, in TE domains 1 and 13, respectively, which can potentially cross any of the domains. One can consider in this example the contribution of, for example, path computation element PCE3 to the path computation process. Because PCE3 does not have end-to-end TE visibility for the potential resulting path, it has no choice but to compute a full set of paths from all potential entry points into its TE visibility area (which are domains 7, 8 and 9) to all potential exit points from the area and to convey the entire path set to the next path computation element PCE, e.g. PCE4, which would augment/multiply the path set. These steps will be repeated on each of the path computation elements PCEs, until the request with the accumulated path set reaches the path computation element PCE5, covering local to the path destination TE domain, where the most optimal path from the set can be selected. The PCE orchestration described above becomes more complex with the increasing number of TE domains and inter-connections between them. The approach gets drastically more complex when it is required to compute more than one diverse path between a source and a destination, and the problem gets practically impossible to solve, when it is required to computer concurrently multiple paths for multiple services depending on a global optimization criterion.
In addition to the deficiencies described above, all conventional approaches based on mapping TE domains on IGP areas have the following drawbacks. They are based on the assumption that a universal TE address space across all domains does exist. This means that when adding new segments to the network, an operator has to coordinate the address assignment with all existing TE domains to avoid any address conflicts. This is very inconvenient and causes more configuration errors with the increasing size of the network. Further, the conventional approaches work under the assumption that all currently unreserved/uncommitted network resources of the network are equally available for all potential clients and services. It is impossible, for example, to ear-mark a set of resources to be available only for internal network building purposes, but not for the services provided for network clients.
Accordingly, there is a need to provide a method and apparatus for scaling traffic engineering, TE, routing in a network which, on the one hand, overcomes the above-mentioned drawbacks and deficiencies and, on the other hand, provides a scalable traffic engineering solution that works equally well on networks of any size.